package leetcode.linked;

import java.util.ArrayList;

/**
 * 2. 两数相加
 * <p>
 * 给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
 * <p>
 * 如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
 * <p>
 * 您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
 * <p>
 * 示例：
 * <p>
 * 输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
 * 输出：7 -> 0 -> 8
 * 原因：342 + 465 = 807
 * <p>
 * 分析：定义一个集合每次存储上一位进过来的数字， 循环去相加两个链表的值， 循环终止条件 当两个链表都为 null && 集合无进位记录时退出循环
 * 定义一个新的链表 进行接住两个链表相加的值
 */
public class Solution2 {

    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {

        ListNode dunmyHead = new ListNode(0);
        ListNode sumDunmyHead = dunmyHead;
        ArrayList<Integer> arrayList = new ArrayList<>();
        while (l1 != null || l2 != null || !arrayList.isEmpty()) {
            int num1 = 0, num2 = 0;
            if (l1 != null) {
                num1 = l1.val;
            }

            if (l2 != null) {
                num2 = l2.val;
            }

            int sum = num1 + num2;
            if (!arrayList.isEmpty()) {
                Integer remove = arrayList.remove(0);
                sum += remove;
            }

            if (sum < 10)
                sumDunmyHead.next = new ListNode(sum);
            else if (sum >= 10) {
                arrayList.add(sum / 10);
                sumDunmyHead.next = new ListNode(sum % 10);
            }
            //都向前移动一位
            if (l1 != null)
                l1 = l1.next;
            if (l2 != null)
                l2 = l2.next;
            sumDunmyHead = sumDunmyHead.next;
        }
        return dunmyHead.next;
    }

    public static void main(String[] args) {
        int[] arr1 = {5};
        int[] arr2 = {5};
        ListNode ls = new ListNode(arr1);
        ListNode ls2 = new ListNode(arr2);
        System.out.println(addTwoNumbers(ls, ls2));
    }

}
